Automated modelling and design procedures involve the initial development of a geometric model of a body and the association therewith of various boundary conditions, material properties, and an indication of allowable error in a subsequent structural analysis. The analysis may then be carried out, automatically, by utilizing an adaptive scheme for producing a mesh that divides the model into a plurality of finite elements, which elements are then individually analyzed.
Ideally, the generation of the mesh should be fully automatic, i.e., one which takes, as an input, a geometric representation of a model with associated mesh control information and then, automatically, produces a valid mesh. One approach to deriving a mesh relies upon the properties of the Delaunay triangulation (see the Frey and Cavendish papers cited below). The Delaunay method is based on triangulating a set of points in the model space to produce a mesh of finite elements which, in a three dimensional case, generally means a set of tetrahedral elements. Thus, the Delaunay method initially generates a set of points and then a triangulation of those points which satisfies the property that a circumsphere containing a tetrahedron contains no mesh points within its volume.
One of the problems with creating such a mesh is assuring that the finite elements are either entirely within or entirely without the boundary of the model, so that those that are without the boundary can be segregated and ignored during a subsequent analysis.
In FIG. 1, a perspective view of an exemplary model is shown, the model having essentially a C-shape. The model is defined by a plurality of vertices, with sets of vertices defining faces of the model (for instance, vertices 10, 12, 14, 16, 18, 20, 22, and 24 define face 26 of the model). As is well known, each vertex is entered as a set of coordinates which define its position in three-dimensional space.
To perform a finite element analysis on the model shown in FIG. 1, the vertices and faces of the model are subjected to a Delaunay tetrahedrization using a known Delaunay mesh generation program. In FIG. 2, a tetrahedron is shown which forms the basic output of the Delaunay method in three dimensions. In FIG. 3, a plan view of face 26 is shown, subsequent to the Delaunay tetrahedrization of the model. During the Delaunay procedure, it often occurs that the formed tetrahedra exhibit edges that cross boundaries of the model. Under such circumstances, such tetrahedra must be found and subdivided so as to fulfill the totally in/totally out criteria. In the case shown in FIG. 3, the tetrahedra defined by vertices 12, 14, 20, and 12, 16, 20 obscure the boundary between vertices 16 and 14. This anomaly must be corrected prior to performing a finite element analysis.
In FIGS. 4a and b, several common "violations" are illustrated which may occur during an initial Delaunay tetrahedrization. In FIG. 4a, an object edge is shown passing through the interior of a Delaunay triangle at a point other than at a vertex of the triangle. In FIG. 4b, a Delaunay triangle edge is shown which passes through a face F of the model, at a point other than at a vertex of face F on a vertex defining the edge. Both of these situations give rise to tetrahedra which violate the totally in/totally out criteria.
The prior art has attempted to cope with the above-defined violations in various ways. One of the earlier methods used to achieve the totally in/totally out criteria was to run the Delaunay procedure on a model and then to have the user examine the model and insert additional vertex points into the mesh to eliminate the violating tetrahedra. Certain prior art references attempt to avoid the problem through "smarter" generation of the initial mesh of points. For instance see the following references: "Automatic Three-Dimensional Mesh Generation by the Modified-Octree Technique", Yerry et al., International Journal For Numerical Methods and Engineering Column, Vol. 20, pp. 1965-1990 (1984); "An Approach To Automatic Three-Dimensional Finite Element Mesh Generation", Cavendish et al., International Journal for Numerical Methods and Engineering, Vol. 21, pp. 329-347 (1985); "Magnetic Field Computation Using Delaunay Triangulation and Complementary Finite Element Methods", Cendes et al., IEEE Transactions on Magnetics, Vol. Mag-19, No. 6, Nov. 1983, pp. 2551-2554; and "Selective Refinement: A New Strategy For Automatic Node Placement in Graded Triangular Meshes", Frey, International Journal for Numerical Methods in Engineering, Vol. 24, pp. 2183-2200 (1987).
In a paper entitled "Implementing Watsons Algorithm in Three Dimensions" by Field, International Journal of Numerical Methods and Engineering, Vol. 26, pp. 2503-2515 (1988), the problem of having tetrahedra near a solid's boundary and having portions of the tetrahedra extend over the boundary are recognized. However, the author only indicates that additional points are required to enable subdivision of such tetrahedra and does not further teach how to insert those points.
In an article entitled "Geometry-Based Fully Automatic Mesh Generation and the Delaunay Triangulation" by Schroeder et al., International Journal for Numerical Methods in Engineering, Vol. 26, pp. 2503-2515, a solution is presented to enable trimming of Delaunay-generated tetrahedra. Schroeder et al. teach that the additional points should be placed at the exact intersection of the boundary of the mesh element and the surface of the model. While this solution does achieve the totally in/totally out criteria, it can lead to a large number of points being added to the mesh. This creates many different tetrahedra at model points which do not necessarily require such detailed subdivisions. As a result, computations during a subsequent finite element analysis are substantially slowed due to the increased number of finite elements to be analyzed.
Other prior art having some bearing on mesh generation and improvements thereof can be found in U.S. Pat. Nos. 4,912,664 to Weiss et al.; 4,888,713 to Falk; 4,697,178 to Heckel and in the following IBM Technical Disclosure Bulletin articles--Vol. 32, No. 1, June 1989 pp. 340-342 (Koyamada) and Vol. 18, No. 4, Sep. 1975, pp. 1163-1175 (Schreiber).
Accordingly, it is an object of this invention to provide an improved finite element generation system wherein the totally in/totally out criteria for generated tetrahedra is automatically satisfied.
It is still another object of this invention to provide an automatic mesh generation system for three dimensional objects wherein the number of added mesh points generated to satisfy the totally in/totally out criteria is minimized.